package com.congee02;

public class Change_DP1 {

    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];

        dp[n][0] = 1;
        for (int j = 1 ; j <= amount ; j ++ ) {
            dp[n][j] = 0;
        }

        for (int index = n - 1 ; index >= 0 ; index -- ) {
            for (int rest = 0 ; rest <= amount ; rest ++ ) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - coins[index] >= 0) {
                    dp[index][rest] += dp[index][rest - coins[index]];
                }
            }
        }
        return dp[0][amount];
    }

    public int process(int[] A, int index, int rest) {
        if (index == A.length) {
            return rest == 0 ? 1 : 0;
        }
        int ret = 0;
        int cost;
        for (int cnt = 0 ; (cost = cnt * A[index]) <= rest ; cnt ++ ) {
            ret += process(A, index + 1, rest - cost);
        }
        return ret;
    }

}
